// https://leetcode.cn/problems/divide-two-integers/
// 
// 题干：给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。


// 示例：
// 输入：dividend = 10, divisor = 3    输出：3


// 碎语：正数负数的边界问题

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <vector>
#include <climits>

class Solution
{
public:
    int divide(int x, int y)
    {
        if (x == INT_MIN && y == -1) return INT_MAX;
        if (x == INT_MIN && y == 1) return INT_MIN;
        if (y == INT_MIN) return x == INT_MIN ? 1 : 0;
        if (x == 0) return 0;

        bool is_minus = false;
        if ((x < 0 && y > 0) || (x > 0 && y < 0))
            is_minus = true;

        x = x < 0 ? x : -x;
        y = y < 0 ? y : -y;

        int res = 0;
        vector<int> exp;

        for (int i = y; i >= x; i = i + i)
        {
            exp.push_back(i);
            if (i < -(1 << 30)) break;
        }

        for (int i = exp.size() - 1; i >= 0; i--)
        {
            if (x <= exp[i])
            {
                x -= exp[i];
                res += 1 << i;
            }
        }

        return is_minus ? -res : res;
    }
};

int main()
{
    cout << Solution().divide(INT_MIN, 2) << endl;

    return 0;
}